package 剑指offer.树;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一棵二叉搜索树，请找出其中的第k大的结点。
 * 例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三大结点的值为 4
 */
public class 第54题二叉搜索树的第K大节点 {


    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }

    List<TreeNode> treeNodes = new ArrayList<>();

    /**
     * 我们注意到题目描述的是二叉搜索树，按照二叉树搜索树的特点（左小右大）
     * 采用中序遍历，可以得到递增的序列，当递增遍历到第 K 个节点时就行了
     * @param pRoot 二叉搜索树的头结点
     * @param k 寻找第几大的数
     * @return
     */
    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot == null || k <= 0) {
            return null;
        }
        Recursive(pRoot);
        if (k > treeNodes.size()) {
            return null;
        } else {
            return treeNodes.get(k - 1);
        }
    }

    /**
     * 按照中序遍历的结果，取第 K 个答案即可
     */
    private void Recursive(TreeNode node) {
        if (node != null) {
            Recursive(node.left);
            treeNodes.add(node);
            Recursive(node.right);
        }
    }

}
